import random
from UAS.algorithm.chromosome import Chromosome

class Selection:
    def __init__(self, population):
        self.population = population
        self.selected = set()
        
    def reset_selection(self):
        self.selected = set()
        
    def random_select(self):
        """随机选择2个未选个体，不放回"""
        candidates = [ind for ind in self.population if ind not in self.selected]
        
        if len(candidates) == 1:
            # Return single candidate as both parents
            self.selected.add(candidates[0])
            return candidates[0], candidates[0]
        elif len(candidates) < 2:
            return None, None
            
        selected = random.sample(candidates, 2)
        self.selected.update(selected)
        return selected[0], selected[1]
        
    def tournament_select(self):
        # 过滤掉已选个体
        candidates = [ind for ind in self.population if ind not in self.selected]
        
        if len(candidates) == 1:
            # Return single candidate as both parents
            self.selected.add(candidates[0])
            return candidates[0], candidates[0]
        elif len(candidates) == 2:
            # Use both candidates as parents
            self.selected.update(candidates)
            return candidates[0], candidates[1]
        elif len(candidates) == 3:
            # Select two parents from three candidates
            selected = random.sample(candidates, 2)
            self.selected.update(selected)
            return selected[0], selected[1]
        elif len(candidates) < 4:
            return None, None
            
        # 随机选择4个未选个体
        selected = random.sample(candidates, 4)
        
        # 标记为已选
        self.selected.update(selected)
        
        # 比较选出父代
        def compare(a, b):
            if a.total_profit != b.total_profit:
                return a if a.total_profit > b.total_profit else b
            return a if a.total_cost < b.total_cost else b
            
        p1 = compare(selected[0], selected[1])
        p2 = compare(selected[2], selected[3])
        
        return p1, p2

class Crossover:
    def __init__(self, valid_points):
        self.valid_points = valid_points
        self.n = len(valid_points)
        
    def LOX(self, p1, p2):
        # 获取起点0和终点1的位置
        start_idx = p1.index(0)
        end_idx = p1.index(1)
        
        # 计算0到1之间的有效路径长度
        if end_idx > start_idx:
            path_len = end_idx - start_idx
        else:
            path_len = self.n - start_idx + end_idx
            
        # 生成C1
        c1 = [None] * self.n
        c1[start_idx] = 0  # 固定起点
        c1[end_idx] = 1    # 固定终点

        if path_len < 3:
            # 路径长度小于3时，直接复制P1中0到1之间的全部元素
            for i in range(start_idx, end_idx + 1):
                c1[i] = p1[i]
        else:
            # 路径长度大于等于3时，保持原有随机逻辑
            copy_start = random.randint(start_idx + 1, start_idx + path_len - 1) % self.n
            # 确保copy_len不超过剩余可用位置
            max_copy_len = path_len - 2  # 减去起点和终点
            copy_len = min(random.randint(path_len // 2, 2 * path_len // 3), max_copy_len)
            
            # 复制P1段到C1，处理循环复制
            copied = 0
            idx = copy_start
            while copied < copy_len:
                if idx == end_idx:  # 遇到1
                    idx = 1  # 跳转到0后面的第一个数（序号1）
                    continue
                if idx >= len(p1):  # 防止越界
                    break
                c1[idx] = p1[idx]
                copied += 1
                idx = (idx + 1) % self.n
                
        # 从P2按顺序填充空白位置
        p2_ptr = 0
        for i in range(self.n):
            if c1[i] is None:
                while p2_ptr < len(p2):
                    if p2[p2_ptr] not in c1:  # 移除对1的过滤
                        if 1 not in c1 or p2[p2_ptr] != 1:  # 如果序列没有1，或者当前值不是1
                            c1[i] = p2[p2_ptr]
                            break
                    p2_ptr += 1
                    if p2_ptr >= len(p2):  # 如果指针越界，跳出循环
                        break
                if c1[i] is None:  # 如果还有空白，随机填充
                    unused = [p for p in self.valid_points if p not in c1]  # 移除对1的过滤
                    if 1 not in c1:  # 如果序列没有1，允许选择1
                        unused.append(1)
                    if unused:
                        c1[i] = random.choice(unused)
                    else:
                        c1[i] = p1[i]
        
        # 生成C2（类似C1的过程）
        c2 = [None] * self.n
        c2[start_idx] = 0  # 固定起点
        c2[end_idx] = 1    # 固定终点
        
        if path_len < 3:
            # 路径长度小于3时，直接复制P2中0到1之间的全部元素
            for i in range(start_idx, end_idx + 1):
                c2[i] = p2[i]
        else:
            # 路径长度大于等于3时，保持原有随机逻辑
            copy_start = random.randint(start_idx + 1, start_idx + path_len - 1) % self.n
            # 确保copy_len不超过剩余可用位置
            max_copy_len = path_len - 2  # 减去起点和终点
            copy_len = min(random.randint(path_len // 2, 2 * path_len // 3), max_copy_len)
            
            # 复制P2段到C2，处理循环复制
            copied = 0
            idx = copy_start
            while copied < copy_len:
                if idx == end_idx:  # 遇到1
                    idx = 1  # 跳转到0后面的第一个数（序号1）
                    continue
                if idx >= len(p2):  # 防止越界
                    break
                c2[idx] = p2[idx]
                copied += 1
                idx = (idx + 1) % self.n
                
        # 从P1按顺序填充空白位置
        p1_ptr = 0
        for i in range(self.n):
            if c2[i] is None:
                while p1_ptr < len(p1):
                    if p1[p1_ptr] not in c2:  # 移除对1的过滤
                        if 1 not in c2 or p1[p1_ptr] != 1:  # 如果序列没有1，或者当前值不是1
                            c2[i] = p1[p1_ptr]
                            break
                    p1_ptr += 1
                    if p1_ptr >= len(p1):  # 如果指针越界，跳出循环
                        break
                if c2[i] is None:  # 如果还有空白，随机填充
                    unused = [p for p in self.valid_points if p not in c2]  # 移除对1的过滤
                    if 1 not in c2:  # 如果序列没有1，允许选择1
                        unused.append(1)
                    if unused:
                        c2[i] = random.choice(unused)
                    else:
                        c2[i] = p2[i]
                        
        return c1, c2
